/*
 * @lc app=leetcode.cn id=28 lang=cpp
 *
 * [28] 实现 strStr()
 */

#include <limits.h>

#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <vector>
#include <algorithm>
using namespace std;

// @lc code=start
class Solution {
public:
    int strStr(string haystack, string needle) {

        // 如果 needle 为空，直接返回 0
        if (needle.size() == 0) {
            return 0;
        }
        // 如果 haystack 为空，直接返回 -1
        if (haystack.size() == 0) {
            return -1;
        }

        // 从首位开始依次遍历第一个字符串
        for (int i = 0; i < haystack.size(); i++) {
            if (haystack[i] == needle[0]) {
                // 首位匹配则开始遍历第二个字符串
                int count = 0;
                int left = i;
                for (int right = 0; right < needle.size(); right++) {
                    // 超出第一个字符串下标 或者 两个字符串中的字符不同
                    if (left > haystack.size() - 1 || haystack[left] != needle[right]) {
                        break;
                    }
                    count++;
                    left++;
                }
                if (count == needle.size()) {
                    return i;
                }
            }
        }
        
        return -1;
    }
};
// @lc code=end

